package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.*;

/**
 * 描述：
 * 给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。
 *
 * @author 🧑 ‍wanwei
 * @since 2023-01-14 10:53
 */
public class CS1481 {


    public static void main(String[] args) {

        int[] arr =  {4,3,1,1,3,3,2};
        int k = 3;
        System.out.println(findLeastNumOfUniqueInts(arr, k));
    }

    public static int findLeastNumOfUniqueInts(int[] arr, int k) {
        //将数字及数量统计排序 从数量最少的数字开始移除
        Map<Integer,Integer> map = new HashMap<>();

        for (int i = 0; i < arr.length; i++) {
            Integer num = map.getOrDefault(arr[i], 0);
            map.put(arr[i],++num);
        }

        List<Integer> list = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            list.add(entry.getValue());
        }
        list.sort(Comparator.naturalOrder());
        int length = 0;
        for (int i = 0; i < list.size(); i++) {
            k = k- list.get(i);
            if(k <0){
                break;
            }
            length++;
        }
        return list.size() - length;
    }
}
